import sys
from collections import defaultdict, deque
N = int(input())
for _ in range(N):
adjList = defaultdict(list)
n ,m = map(int, input().split())
for _ in range(m):
u, v, s = input().split()
u, v = int(u), int(v)
d = 1 if s == 'imposter' else 0
adjList[u].append((v, d))
adjList[v].append((u, d))
role = [None] * (n+1)
ans = 0
flag = False
for i in range(1, n+1):
if role[i] is not None:
continue
q = deque([(i, 0)])
role[i] = 0
maxx = [0, 0]
while q:
u, r = q.popleft()
maxx[r] += 1
for v, d in adjList[u]:
if role[v] is None:
role[v] = (r + d) % 2
q.append((v, role[v]))
elif role[v] != (r + d) % 2:
print(-1)
flag = True
break
if flag:
break
if flag:
break
ans += max(maxx)
if flag:
continue
print(ans + sum([1 for i in range(1, n+1) if role[i] is None]))
#include <iostream>
#include <bits/stdc++.h>
#define bg begin()
#define e end()
#define sz(x) (int)x.size()
#define pb push_back
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define repd(i, r, l) for(int i = r; i >= l; i--)
#define endl "\n"
#define fi first
#define se second
#define mp make_pair
#define getbit(x, i) (x & (1 << i))
#define cntbit __builtin_popcount
#define clr(x, i) memset(x, i, sizeof(x))
#define debug(x) cerr << #x << " = " << (x) << endl
#define task "main"
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <double, int> pld;
template <class T> void mini(T &a, T b) {if(a > b) a = b;}
template <class T> void maxi(T &a, T b) {if(a < b) a = b;}
const int N = 7E5 + 2;
const int inf = 1E9 + 7;
const ll mod = 1E9 + 7;
const ll oo = 1E18 + 7;
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
//===========================================//
int n, m;
bool ok = true;
vector <int> g[N];
int color[N], c[2];
//===========================================//
void Inp()
{
cin >> n >> m;
int fake = n + 1;
rep(i, 1, n + m) g[i].clear();
rep(i, 1, m)
{
int x, y; string s; cin >> x >> y >> s;
if(s == "imposter")
{
g[x].pb(y);
g[y].pb(x);
}
else
{
g[fake].pb(x);
g[fake].pb(y);
g[x].pb(fake);
g[y].pb(fake);
fake++;
}
}
clr(color, -1);
}
void DFS(int u)
{
if(u <= n) c[color[u]]++;
rep(i, 0, sz(g[u]) - 1)
{
int v = g[u][i];
if(color[v] == -1)
{
color[v] = (color[u] ^ 1);
DFS(v);
}
else if(color[v] == color[u])
{
ok = false;
return;
}
}
}
void Solve()
{
ok = true;
int res = 0;
rep(i, 1, n)
{
if(color[i] == -1)
{
color[i] = 0;
c[0] = c[1] = 0;
DFS(i);
res += max(c[1], c[0]);
}
}
if(ok) cout << res << endl;
else cout << -1 << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
cin >> T;
while(T--)
{
Inp();
Solve();
}
// cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
2148. Count Elements With Strictly Smaller and Greater Elements | 2149. Rearrange Array Elements by Sign |
2150. Find All Lonely Numbers in the Array | 2151. Maximum Good People Based on Statements |
2144. Minimum Cost of Buying Candies With Discount | Non empty subsets |
1630A - And Matching | 1630B - Range and Partition |
1630C - Paint the Middle | 1630D - Flipping Range |
1328A - Divisibility Problem | 339A - Helpful Maths |
4A - Watermelon | 476A - Dreamoon and Stairs |
1409A - Yet Another Two Integers Problem | 977A - Wrong Subtraction |
263A - Beautiful Matrix | 180C - Letter |
151A - Soft Drinking | 1352A - Sum of Round Numbers |
281A - Word Capitalization | 1646A - Square Counting |
266A - Stones on the Table | 61A - Ultra-Fast Mathematician |
148A - Insomnia cure | 1650A - Deletions of Two Adjacent Letters |
1512A - Spy Detected | 282A - Bit++ |
69A - Young Physicist | 1651A - Playoff |